DATABASE ORGANIZATION, RECORD ACCESS
Database management, or transaction processing, systems are well known. These systems are generally utilized to provide rapid access to database tables which contain a plurality of data records. A relational transaction processing system provides access to multiple database tables, where elements of one database table are generally related to elements in another database table. A relational database allows a user to search, access, and alter data contained in multiple database tables using one or more specific elements or fields. One important aspect of all such database systems is the ability of the system to provide rapid and efficient access to individual records in each database. Recently, database management systems (DBMS) and relational database management systems (RDBMS) have been provided, which support the utilization of the database by multiple users simultaneously, allowing users to access specific data concurrently.
An index file is commonly used by database management programs to provide quick and efficient access to records in tables of the database, which are said to be indexed by the index file. The index file corresponds to one or more fields of the database table and facilitates database searching by arranging the values of the fields in a contiguous sequence. These index files are commonly configured in a multi-level B-Tree structure. An index file configured as a B-Tree structure includes a root node, and many levels of nodes branching from the root node. The information contained in these nodes includes pointers to the nodes at the next level, or pointers to the records in the database. These pointers include further information, termed key record information, which may reference the records in the database. The record keys are in an ordered form throughout the nodes.
For example, an index tree (FIG. 1) may be built to provide an alphabetic listing of employee names stored in the records of a database. A root node 2 includes reference keyed data that relates to records directly or indirectly referenced by the next level 4 of nodes. The reference keys contain information about the indexed field, which on the index tree of FIG. 1 is the spelling of employees' names. Therefore, the ordered keys in the root node 2 point to the next successive level 4 of nodes.
In the example of FIG. 1, a first successive node 6 indirectly or directly references all employee names beginning with A, B, or C. A next successive node 8, parallel with the first successive node 6, contains employee records for employees whose last names begin with the letters D through M. A last successive node 10 on the level 4 references records of employees whose last names begin with N through Z. As a user searches through successive levels of nodes in the index file tree, a bottom node, or "leaf node," is eventually reached. The contents of this bottom node include record keys that point to the individual records in storage. For instance, a leaf node 12 in FIG. 1 includes a key that points to the individual employee record for the employee Arthur Able.
AN EXAMPLE OF A DATABASE OPERATION
Consider the following set-oriented Structured Query Language (SQL) delete statement:
where T1 is the name of a table containing a set of data records, including a column (field) C1 having numerical values corresponding to individual records of the table. Assume that an index on C1 exists (call it I1) and that the RDBMS includes an optimizer that chooses to use I1 and perform a range scan to determine the set of records to be deleted whose C1 value satisfies the specified range condition (i.e., C1 value lies between 10 and 20). These sorts of deletes are very commonly issued by RDBMS users.
Deletes like these are also generated internally by RDBMSs to implement referential integrity (i) when cascade-on-delete is the rule and there is an index on the foreign key of the child table, (ii) where that key is the primary key of the parent table, and (iii) where a parent record deletion's effect needs to be propagated to the child table.
The conventional approach to execution of such a statement would include traversing the index tree structure to find a record to which the command applies. When the appropriate index key is found, the corresponding record, following appropriate index and record locking is deleted. The index key corresponding to the deleted record is also then deleted. This requires re-traversing the index tree to relocate the key. Using an iterator to keep track of each database record being deleted, this tree multi-pass tree traversal and locking process is thereafter repeated until all records satisfying the command parameters, and their corresponding keys, are deleted.
This example represents the state of the art in terms of computing performance. However, the conventional execution strategy may require as many as 3N data lock calls and 4N index lock calls, together with as many as N root to leaf traversals, where N is the number of records to be deleted. These lock calls and index traversals consume a disadvantageously large amount of processing time, and have been a source of dissatisfaction to customers of operating systems and data base systems.